package com.njupt.twoStage.BinarySearch;

import java.util.Arrays;

public class SearchRange {

    /**
     * 解法1：使用二分查找，找到需要查找的元素，然后分别往左右遍历查找
     * @param nums
     * @param target
     * @return
     */
    public int[] searchRange(int[] nums, int target) {

        int index = binarySearch(nums, target);
        System.out.println(index);

        //如果二分搜索失败，则直接返回
        if(index==-1){
            return new int[] {-1,-1};
        }
        //查找左右边界
        int left = index;
        int right = index;

        // int[] nums = {-1,0,0,3,5,9,12};
        while (left-1>=0 && nums[left-1] == target){left--;}

        while(right+1 <= nums.length-1 && nums[right+1] == target){right++;}

        return new int[] {left,right};
    }


    //左闭，右闭区间
    public static int binarySearch(int[] nums,int target){
        int left = 0;
        int right = nums.length-1;
        int mid;
        while(left<=right){
            mid = (left + right)/2;
            if(nums[mid] == target){
                return mid;
            }else if(nums[mid]>target){
                right = mid -1;
            }else {
                left = mid + 1;
            }
        }
        return -1;
    }

    //找右端区间
    public static int getRightBorder(int[] nums,int target){

        int left = 0;
        int right = nums.length-1;
        int righterBorder = -1;
        int mid;
        while (left<=right){
            mid = (right+left)/2;
            if(target<nums[mid]){
                right = mid -1;
            }else {
                left = mid +1;
                righterBorder = left;
            }
        }
        return righterBorder;
    }

    //查找左端区间
    public static int getLeftBorder(int[] nums,int target){
        int left = 0;
        int right = nums.length-1;
        int leftBorder = -1;
        int mid;
        while (left<=right){
            mid = (left+right)/2;
            if(target>nums[mid]){
                left = mid +1;
            }else {
                right = mid -1;
                leftBorder = right;
            }
        }
        return leftBorder;
    }



//    public static int binarySearch1(int)
    public static void main(String[] args) {
        int[] nums = {-1,0,0,3,5,9,12};

        SearchRange searchRange = new SearchRange();
        int[] ints = searchRange.searchRange(nums, 0);
        System.out.println(Arrays.toString(ints));
    }

}
